/**
 * @author tmh
 * @date 2024/9/20 19:17
 * @description
 */
public class T5最长回文子串 {
    /**
     * 暴力解法
     * lc的测试用例过不完，回超时
     *
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
        String manStr = "";
        int right = 0, left = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                String temp = s.substring(j, i + 1);
                if (isValid(temp)) {
                    if (i - j > right - left) {
                        left = j;
                        right = i;
                    }
                }
            }

        }
        return s.substring(left, right + 1);
    }

    /**
     * 中心拓展
     *
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        //定义回文字符串的左右下标
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            //单个字符为中心拓展
            int len1 = expand(s, i, i);
            //两个字符的的中间拓展
            int len2 = expand(s, i, i + 1);
            //最长长度
            int len = Math.max(len1, len2);
            if (end - start < len) {
                //这个公式背诵就好了
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);

    }


    /**
     * 动态规划
     *
     * @param s
     * @return dp[i][j]表示以i为结尾和以j结尾的最长公共后缀的长度
     * 如果以i为结尾的字符串和以j结尾的字符串的最后一个字符的不相同，那么公共后缀的长度为0
     */
    public String longestPalindrome3(String s) {
        //待定
        return null;
    }


    public int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }


    public boolean isValid(String str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }

}
